/*
    libnbds
    Non-blocking Data Structures Library

    Copyright (C) 2011 Paweł Dziepak

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef NBDS_RCU_H
#define NBDS_RCU_H

#include <list>
#include "list.h"
#include "lifo.h"

namespace nbds {
	template<typename T>
	class rcu_rc;
	class rcu_rc_base;

	template<typename T>
	class rcu_hp;
	class rcu_hp_base;

	class rcu_ptr_base {
	protected:
		void *mobj;
		void *cobj;

		rcu_ptr_base(const rcu_ptr_base &b) : mobj(b.mobj), cobj(b.cobj) { }
		rcu_ptr_base(void *mo, void *co) : mobj(mo), cobj(co) { }

		friend class rcu_rc_base;
		friend class rcu_ticket_base;
	};

	template<typename T>
	class rcu_ptr : public rcu_ptr_base {
	public:
		rcu_ptr(const rcu_ptr_base &b) : rcu_ptr_base(b) { }
		rcu_ptr(const rcu_ptr<T> &x) : rcu_ptr_base(x.mobj, x.cobj) { }

		rcu_ptr<T> &operator=(const rcu_ptr<T> &x) {
			if (&x != this) {
				mobj = x.mobj;
				cobj = x.cobj;
			}
			return *this;
		}

		T &operator*() {
			return *reinterpret_cast<T*>(mobj);
		}

		T *operator->() {
			return reinterpret_cast<T*>(mobj);
		}

		const T &operator*() const {
			return *reinterpret_cast<T*>(mobj);
		}

		const T *operator->() const {
			return reinterpret_cast<T*>(mobj);
		}
	};

	/* Reference counting based implementation */

	class rcu_rc_base {
	private:
		struct ptr_cell {
			void *obj;
			int counter;
		};

		list<ptr_cell*> cells;
		ptr_cell *current_cell;

		void (*delete_obj)(void*);
		void *(*copy_obj)(void*);
	protected:
		rcu_rc_base(void *p, void (*)(void*), void *(*)(void*));

		rcu_ptr_base lock_write_();
		rcu_ptr_base lock_read_();

		bool release_write_(rcu_ptr_base &obj);
		void release_read_(const rcu_ptr_base &obj);	
	};

	template<typename T>
	class rcu_rc : public rcu_rc_base {
	private:
		static void del_obj(void *obj) {
			delete reinterpret_cast<T*>(obj);
		}

		static void *cpy_obj(void *obj) {
			return new T(*reinterpret_cast<T*>(obj));
		}
	
	public:
		rcu_rc(T *p) : rcu_rc_base(reinterpret_cast<void*>(p),
						&del_obj, &cpy_obj) { }

		rcu_ptr<T> lock_write() {
			return rcu_ptr<T>(lock_write_());
		}

		const rcu_ptr<T> lock_read() {
			return rcu_ptr<T>(lock_read_());
		}

		bool release_write(rcu_ptr<T> &obj) {
			return release_write_(static_cast<rcu_ptr_base&>(obj));
		}

		void release_read(const rcu_ptr<T> &obj) {
			return release_read_(static_cast<const rcu_ptr_base&>(obj));
		}
	};

	/* Hazard pointers based implementation */

	class rcu_ticket_base {
	private:
		void **hazard_pointer;

		rcu_hp_base *base;

		std::list<void*> retired;
	public:
		rcu_ticket_base(rcu_hp_base*, void**);
		rcu_ticket_base(const rcu_ticket_base &);
		void release();

		rcu_ptr_base lock_write_();
		rcu_ptr_base lock_read_();

		bool release_write_(rcu_ptr_base &obj);
		void release_read_(const rcu_ptr_base &obj);
	};

	template<typename T>
	class rcu_ticket : public rcu_ticket_base {
	public:
		rcu_ticket(rcu_hp<T> *b, void **hp) :
			rcu_ticket_base(b, hp) { }

		rcu_ticket(const rcu_ticket<T> &x) :
			rcu_ticket_base(x) { }

		rcu_ptr<T> lock_write() {
			return rcu_ptr<T>(lock_write_());
		}

		const rcu_ptr<T> lock_read() {
			return rcu_ptr<T>(lock_read_());
		}

		bool release_write(rcu_ptr<T> &obj) {
			return release_write_(static_cast<rcu_ptr_base&>(obj));
		}

		void release_read(const rcu_ptr<T> &obj) {
			return release_read_(static_cast<const rcu_ptr_base&>(obj));
		}
	};

	class rcu_hp_base {
	private:
		void *obj;

		list<void*> hzrd_ptrs;
		lifo<void**> free_hps;

		void (*delete_obj)(void*);
		void *(*copy_obj)(void*);
	protected:
		rcu_hp_base(void *p, void (*)(void*), void *(*)(void*));

		void **get_ticket_();
		void release_ticket_(void **);

		friend class rcu_ticket_base;
	};

	template<typename T>
	class rcu_hp : public rcu_hp_base {
	private:
		static void del_obj(void *obj) {
			delete reinterpret_cast<T*>(obj);
		}

		static void *cpy_obj(void *obj) {
			return new T(*reinterpret_cast<T*>(obj));
		}
	
	public:
		rcu_hp(T *p) : rcu_hp_base(reinterpret_cast<void*>(p),
						&del_obj, &cpy_obj) { }

		rcu_ticket<T> get_ticket() {
			return rcu_ticket<T>(this, get_ticket_());
		}
	};
}

#endif
